#include<stdio.h>
#include<malloc.h>
#include<string.h>

int do_del = 0;

typedef struct NODE node;
struct NODE{
    int data;
    node* left;
    node* right;
};

node* new_node(){
    node* r = malloc(sizeof(node));
    r->left = r->right = NULL;
    return r;
}

node* LL(node* root){
    node*A,*B,*R;
    A = root; B = root->left; R = B->right;
    B->right = A; A->left = R;
    return B;
}

node* RR(node* root){
    node*A,*B,*L;
    A = root; B = root->right; L = B->left;
    B->left = A; A->right = L;
    return B;
}

node* LR(node* root){
    node*A,*B,*C,*L,*R;
    A = root; B = A->left; C = B->right; L = C->left; R = C->right;
    C->left = B; C->right = A; B->right = L; A->left = R;
    return C;
}

node* RL(node* root){
    node*A,*B,*C,*L,*R;
    A = root; B = A->right; C = B->left; L = C->left; R = C->right;
    C->left = A; C->right = B; A->right = L; B->left = R;
    return C;
}

void tree_del(node* t){
    if(t==NULL)return;
    if(t->left!=NULL)tree_del(t->left);
    if(t->right!=NULL)tree_del(t->right);
    free(t);
}

int height(node* root){
    if(root==NULL)return 0;
    int l = height(root->left);
    int r = height(root->right);
    if(l<r)l=r;
    return l+1;
}

int diff(node* root){
    if(root==NULL)return 0;
    return height(root->left) - height(root->right);
}

node* balance(node* root){
    int dif = diff(root);
    if(dif > 1)if(diff(root->left)>0)root = LL(root);else root = LR(root);
    else if(dif<-1)if(diff(root->right)>0)root = RL(root);else root = RR(root);
    return root;
}

node* insert(node* root,int v){
    if(root==NULL){
        root = new_node();
        root->data = v;
    }else if(root->data > v){
        root->left = insert(root->left,v);
        root = balance(root);
    }else{
        root->right = insert(root->right,v);
        root = balance(root);
    }
    return root;
}

void pre_order_traverse(const node* root){
    if(root==NULL)return;
    printf("%d ",root->data);
    pre_order_traverse(root->left);
    pre_order_traverse(root->right);
}


void in_order_traverse(const node* root){
    if(root==NULL)return;
    in_order_traverse(root->left);
    printf("%d ",root->data);
    in_order_traverse(root->right);
}

void post_order_traverse(const node* root){
    if(root==NULL)return;
    post_order_traverse(root->left);
    post_order_traverse(root->right);
    printf("%d ",root->data);
}


void print_tree(const node* t){
    if(t==NULL){putchar('*');return;}
    printf("(%d",t->data);
    if(t->left==NULL && t->right==NULL){putchar(')');return;}
    print_tree(t->left);
    print_tree(t->right);
    putchar(')');
}

node* search(node* root,int b){
    if(root==NULL)return NULL;
    if(root->data == b)return root;
    return (root->data > b) ? search(root->left,b) : search(root->right,b);
}


// usage: root = del_by_value_non_recursive(root,b);
node* del_by_value_non_recursive(node* root,int b){
    if(root==NULL)return NULL;

    if(root->data == b){
        node* r = root;
        if(root->left){
            root = root->left;
            if(root->right){while(root->right->right)root = root->right;}
            root->right = r->right;
            root = r->left;
            free(r);
            return root;
        }else if(root->right){
            root = root->right;
            if(root->left){while(root->left->left)root = root->left;}
            root->left = r->left;
            root = r->right;
            free(r);
            return root;
        }else{
            free(root);return NULL;
        }
    }

    node *p,*q;p = q = root;int is_left = 0;
    while(root && root->data != b){
        if(root->data>b){p = root;root = root->left;is_left = 1;}
        else {p = root;root = root->right;is_left = 0;}
    }
    if(root==NULL)return q;

    node* r = root;
    if(root->left){
        root = root->left;
        if(root->right){while(root->right->right)root = root->right;}
        root->right = r->right;
        root = r->left;
    }else if(root->right){
        root = root->right;
        if(root->left){while(root->left->left)root = root->left;}
        root->left = r->left;
        root = r->right;
    }else root = NULL;
    free(r);
    if(is_left)p->left = root;else p->right = root;
    return q;
}


int main(int argc,char** argv){
    if(argc==2&& ( strcmp(argv[1],"-d")==0) )do_del=1;
    int n,buf;
    printf("Enter number of integers: ");
    scanf("%d",&n);
    node* root = NULL;
    while(n--){scanf("%d",&buf);root = insert(root,buf);}
    print_tree(root);putchar('\n');
    printf("Pre-order traverse: ");pre_order_traverse(root);
    printf("\nIn-order traverse: ");in_order_traverse(root);
    printf("\nPost-order traverse: ");post_order_traverse(root);putchar('\n');
    if(!do_del)while(printf("Enter search key: ")&&scanf("%d",&buf)==1){print_tree(search(root,buf));putchar('\n');}
    else while(printf("Enter delete key: ")&&scanf("%d",&buf)==1){
        root = del_by_value_non_recursive(root,buf);
        print_tree(root);putchar('\n');
    }
    
    tree_del(root);
    return 0;
}
